#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include"linklist Node.h"
#include<cstdlib>
#include<iostream>

using namespace std;

template <typename ElemType>
class LinkList {

	typedef Node<ElemType> *Position;

public:
	LinkList();
	~LinkList();

	Status isEmpty() const;
	Status isLast(const Position p) const;

	Position Find(const ElemType key) const{
		Position temp = m_pHead->getNext();

		while (temp != NULL && temp->getData() != key) {
			temp = temp->getNext();
		}

		return temp;
	}
	Position FindPrevious(const ElemType key) const {
		Position temp = m_pHead, p = m_pHead->getNext();

		while (p->getData() != key && p != NULL) {
			temp = p;
			p = p->getNext();
		}
		if (p == NULL) {
			cout << "Can't find this node, will return a pointer to the head! " << endl;
			return m_pHead;
		}
		else {
			return temp;
		}
	}
	Position FindPrevious(const Position &cur) const{
		Position point = m_pHead;
		while (point->getNext() != cur) {
			point = point->getNext();
		}
		return point;
	}
	void Delete(const ElemType key);
	void Delete(const ElemType mink, const ElemType maxk);
	void Insert(const ElemType key);
	void Insert(const ElemType key, const Position p);
	void Insert(const int sort_way, const ElemType key);
	void Reverse();

	void show_data() const;
	void addLength();
	void cutLength();
	int getLength() const;
private:
	Position m_pHead;
	Position m_pTail;
	int  m_iLength;
	
};

template <typename ElemType>
LinkList<ElemType>::LinkList():m_iLength(0){
	m_pHead = new Node<ElemType>;
	if (m_pHead == NULL) {
		perror("Failed to allocate memory!\n");
		exit(EXIT_FAILURE);
	}
	m_pTail = m_pHead;
	m_pHead->setData(0.0);
	m_pHead->setNext(NULL);
}

template <typename ElemType>
LinkList<ElemType>::~LinkList() {
	Position temp = m_pHead->getNext();
	Position cur = m_pHead;
	for (;;) {
		delete cur;
		if (temp == NULL) {
			cur = NULL;
			break;
		}
		cur = temp;
		temp = temp->getNext();
	}
}

template <typename ElemType>
Status LinkList<ElemType>::isEmpty() const {
	return m_pHead == m_pTail;
}

template <typename ElemType>
Status LinkList<ElemType>::isLast(const Position p) const {
	return p == m_pTail;
}

template <typename ElemType>
void LinkList<ElemType>::Delete(const ElemType key){
	Position temp = m_pHead, p = m_pHead->getNext();

	while (p->getData() != key && p != NULL) {
		temp = p;
		p = p->getNext();
	}
	if (p == NULL) {
		cout << "Can't find this node! Failed to delete it!" << endl;
	}
	else {
		temp->setNext(p->getNext());
		delete p;
		p = NULL;
	}
	cutLength();
}

template <typename ElemType>
void LinkList<ElemType>::Delete(const ElemType mink,const ElemType maxk) {
	Position cur = m_pHead->getNext(), temp, pre = m_pHead;
	int count = 0;
	if (mink > maxk) {
		cout << "Range error! please check it out!" << endl;
		return;
	}

	while (cur != NULL) {

		if (cur->getData() > mink && cur->getData() < maxk) {
			++count;
			cutLength();
			temp = cur->getNext();
			delete cur;
			if (isLast(cur)) {
				m_pTail = FindPrevious(cur);
			}
			cur = temp;
			pre->setNext(cur);
		}
		else {
			pre = cur;
			cur = cur->getNext();
		}
	}

	cout << "\nTotal Delete: " << count << endl;
}

template <typename ElemType>
void LinkList<ElemType>::Insert(const ElemType key) {
	Node<ElemType> *NewNode = new Node<ElemType>;
	if (NewNode == NULL) {
		perror("Failed to allocate memory!\n");
	}
	else {
		addLength();
		m_pTail->setNext(NewNode);
		m_pTail = NewNode;
		NewNode->setData(key);
		NewNode->setNext(NULL);
	}
}

template <typename ElemType>
void LinkList<ElemType>::Insert(const ElemType key, const Position p) {
	Node<ElemType> *NewNode = new Node<ElemType>;
	if (NewNode == NULL) {
		perror("Failed to allocate memory!\n");
	}
	else {

		NewNode->setData(key);
		NewNode->setNext(p->getNext());
		p->setNext(NewNode);
		addLength();
		if (p == m_pTail) {
			m_pTail = NewNode;
		}
	}
}

template <typename ElemType>
void LinkList<ElemType>::Insert(const int sort_way, const ElemType key) {
	Position temp = new Node<ElemType>;
	if (temp == NULL) {
		perror("Failed to allocate memory!\n");
		return;
	}
	temp->setData(key);
	temp->setNext(NULL);

	if (isEmpty()) {
		m_pHead->setNext(temp);
		m_pTail = temp;
		addLength();
		return;
	}
	Position pre = m_pHead, after = pre->getNext();
	if (sort_way == up) {
		while (after->getNext() != NULL) {
			if (pre->getData() <= key && after->getData() >= key) {
				pre->setNext(temp);
				temp->setNext(after);
				addLength();
				return;
			}
			else {
				pre = after;
				after = after->getNext();
			}
		}
		if (after->getNext() == NULL) {
			if (after->getData() <= key) {
				m_pTail->setNext(temp);
				m_pTail = temp;
			}
			else {
				temp->setNext(after);
				pre->setNext(temp);
			}
		}
	}
	else if (sort_way == down) {
		while (after->getNext() != NULL) {
			if (pre->getData() >= key && after->getData() <= key) {
				pre->setNext(temp);
				temp->setNext(after);
				addLength();
				return;
			}
			else {
				pre = after;
				after = after->getNext();
			}
		}
		if (after->getNext() == NULL) {
			if (after->getData() >= key) {
				m_pTail->setNext(temp);
				m_pTail = temp;
			}
			else {
				temp->setNext(after);
				pre->setNext(temp);
			}
		}
	}
	addLength();
}

template <typename ElemType>
void LinkList<ElemType>::show_data() const {
	Position temp = m_pHead->getNext();
	cout << endl;
	while (temp != NULL) {
		cout << temp->getData() << ' ';
		temp = temp->getNext();
	}
	cout << "Total : " << getLength() << endl;
}

template <typename ElemType>
void LinkList<ElemType>::Reverse() {
	int len = getLength();
	if (len == 0 || len == 1) {
		return;
	}
	Position pre = m_pHead, cur = pre->getNext(), after = cur->getNext();
	while (after != NULL) {
		if (pre == m_pHead) {
			cur->setNext(NULL);
		}
		else {
			cur->setNext(pre);
		}
		pre = cur;
		cur = after;
		after = after->getNext();
	}
	cur->setNext(pre);
	m_pTail = m_pHead->getNext();
	m_pHead->setNext(cur);
}

template <typename ElemType>
void LinkList<ElemType>::addLength() {
	++m_iLength;
}

template <typename ElemType>
void LinkList<ElemType>::cutLength() {
	--m_iLength;
}

template <typename ElemType>
int LinkList<ElemType>::getLength() const {
	return m_iLength;
}


#endif
